/**
 * describe:
 *
 * @author chaP
 * @date 2019/04/07
 */
package CodingTest.AC20190407;

import java.util.Arrays;

public class singleNumber {
    public int[] singleNumber1(int[] nums){
        Arrays.sort(nums);
        int[] res = new int[2];
        int j =0;
        for(int i = 0;i<nums.length-1;i++){
            if(nums[i] == nums[i+1]) i++;
            else res[j++] = nums[i];
        }
        if(nums[nums.length-1] != nums[nums.length-2]) res[j] = nums[nums.length-1];
        return res;
    }
    /**
     * 方法二：
     * 思路：https://blog.csdn.net/qq_38595487/article/details/81163737
     */


    public int[] singleNumbe2(int [] nums) {
        int xor = 0;
        for(int e:nums)
            xor ^= e;
        int []res = new int[2];
        //flag为两个不相同数x，y的最右不同的位，根据这个位异或来划分两组数，一组含x，一组含y
        //因为假设x的不同位为1，其他都为0，则与flag &运算只有不同位运算之后得出1，而y则得出0；
        int flag = xor&(-xor);
        for(int e:nums){
            if((e&flag)==0) res[0] ^=e;
            else res[1]^=e;
        }
        return res;

    }

    public static void main(String[] args) {
        singleNumber sn = new singleNumber();
        int [] nums = {1,2,1,2,4,5};
        int[] res = sn.singleNumbe2(nums);
        for(int i = 0;i<2;i++){
            System.out.println(res[i]);
        }
    }
}
